๋ฌธ์
๋ ๊ฐ์ ๋จ์ด begin, target๊ณผ ๋จ์ด์ ์งํฉ words๊ฐ ์์ต๋๋ค. ์๋์ ๊ฐ์ ๊ท์น์ ์ด์ฉํ์ฌ begin์์ target์ผ๋ก ๋ณํํ๋ ๊ฐ์ฅ ์งง์ ๋ณํ ๊ณผ์ ์ ์ฐพ์ผ๋ ค๊ณ ํฉ๋๋ค.
- ํ ๋ฒ์ ํ ๊ฐ์ ์ํ๋ฒณ๋ง ๋ฐ๊ฟ ์ ์์ต๋๋ค.
- words์ ์๋ ๋จ์ด๋ก๋ง ๋ณํํ ์ ์์ต๋๋ค.
์๋ฅผ ๋ค์ด begin์ด "hit", target๊ฐ "cog", words๊ฐ ["hot","dot","dog","lot","log","cog"]๋ผ๋ฉด "hit" -> "hot" -> "dot" -> "dog" -> "cog"์ ๊ฐ์ด 4๋จ๊ณ๋ฅผ ๊ฑฐ์ณ ๋ณํํ ์ ์์ต๋๋ค.
๋ ๊ฐ์ ๋จ์ด begin, target๊ณผ ๋จ์ด์ ์งํฉ words๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ต์ ๋ช ๋จ๊ณ์ ๊ณผ์ ์ ๊ฑฐ์ณ begin์ target์ผ๋ก ๋ณํํ ์ ์๋์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ๊ฐ ๋จ์ด๋ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
- ๊ฐ ๋จ์ด์ ๊ธธ์ด๋ 3 ์ด์ 10 ์ดํ์ด๋ฉฐ ๋ชจ๋ ๋จ์ด์ ๊ธธ์ด๋ ๊ฐ์ต๋๋ค.
- words์๋ 3๊ฐ ์ด์ 50๊ฐ ์ดํ์ ๋จ์ด๊ฐ ์์ผ๋ฉฐ ์ค๋ณต๋๋ ๋จ์ด๋ ์์ต๋๋ค.
- begin๊ณผ target์ ๊ฐ์ง ์์ต๋๋ค.
- ๋ณํํ ์ ์๋ ๊ฒฝ์ฐ์๋ 0๋ฅผ return ํฉ๋๋ค.
์ ์ถ๋ ฅ ์
| begin | target | words | return |
|---|---|---|---|
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
| "hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
๐ Logic
private int dfs(String begin, String target, String[] words, boolean[] visited, int count, int idx) {
if (begin.equals(target) || visited[idx]) return count;
visited[idx] = true;
int ans = 0;
for (int i = 0; i < words.length; i++) {
if (idx != i && !visited[i] && isOneCharDiff(begin, words[i]))
ans = dfs(words[i], target, words, visited, count + 1, i);
}
return ans;
}
-
์ฌ๊ท์ ์ธ DFS๋ฅผ ์ด์ฉํด ํ์ฌ ๋จ์ด์ ํ ๋ฌธ์๋ง ๋ค๋ฅธ ๋จ์ด๋ก ๋ณํ์ ์ํํ๋ค.
- ์ด๋ ์ง๊ธ๊น์ง์ ๋ณํ๋ ์(
count)๋ฅผ ํจ๊ป ์ ๋ฌํ๋ค.
- ์ด๋ ์ง๊ธ๊น์ง์ ๋ณํ๋ ์(
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
boolean[] visited;
int answer = words.length + 1;
for (int i = 0; i < words.length; i++) {
visited = new boolean[words.length];
if (isOneCharDiff(begin, words[i]))
answer = Math.min(answer, dfs(words[i], target, words, visited, 1, i));
}
if (answer == words.length + 1) return 0;
return answer;
}
private int dfs(String begin, String target, String[] words, boolean[] visited, int count, int idx) {
if (begin.equals(target) || visited[idx]) return count;
visited[idx] = true;
int ans = 0;
for (int i = 0; i < words.length; i++) {
if (idx != i && !visited[i] && isOneCharDiff(begin, words[i]))
ans = dfs(words[i], target, words, visited, count + 1, i);
}
return ans;
}
private boolean isOneCharDiff(String str1, String str2) {
int count = 0;
for (int i = 0; i < str1.length() && count < 2; i++)
if (str1.charAt(i) != str2.charAt(i)) count++;
return count == 1;
}
}
โ๏ธ Review
- ๋จ์ด๋ณ ๋ค๋ฅธ ๋ฌธ์ ์๋ฅผ ๊ทธ๋ํ ํํ๋ก ๋ณํํด ์ ์ฅํ๊ณ ์ด๋ฅผ BFS ๋ฐฉ์์ผ๋ก ์ ๊ทผํ๋๋ก ๊ตฌํํ๋๋ฐ, ๋ฐฉ๋ฒ ์์ฒด๊ฐ ์๋ชป ๋ ๊ฒ ๊ฐ์๋ค.
- ํ ๋ฌธ์๋ง ๋ค๋ฅธ ๋จ์ด๋ก ๋ณํํ ์ ์๊ธฐ์ ๊ตณ์ด ๋จ์ด๋ณ ๋ค๋ฅธ ๋ฌธ์ ์๋ฅผ ๊ตฌํ ํ์๊ฐ ์์๊ณ DFS๋ฅผ ์ด์ฉํ๋ ๋ฐฉ๋ฒ์ ์ฐธ๊ณ ํ๋ค.
๐ ์ถ์ฒ
Programmers : https://programmers.co.kr/learn/courses/30/lessons/43163